package Leetcode.Dichotomy;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/4/11 14:07
 * @Description:
 * 找出第 K 小的数对距离
 * 困难
 * 相关标签
 * 相关企业
 * 提示
 * 数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
 *
 * 给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,3,1], k = 1
 * 输出：0
 * 解释：数对和对应的距离如下：
 * (1,3) -> 2
 * (1,1) -> 0
 * (3,1) -> 2
 * 距离第 1 小的数对是 (1,1) ，距离为 0 。
 * 示例 2：
 *
 * 输入：nums = [1,1,1], k = 2
 * 输出：0
 * 示例 3：
 *
 * 输入：nums = [1,6,1], k = 3
 * 输出：5
 *
 *
 * 提示：
 *
 * n == nums.length
 * 2 <= n <= 104
 * 0 <= nums[i] <= 106
 * 1 <= k <= n * (n - 1) / 2
 */

public class smallestDistancePair {
    public static void main(String[] args) {
        int[] nums = {1, 3, 1};
        int k = 1;
        System.out.println(smallestDistancePair(nums, k));
    }
    public static int smallestDistancePair(int[] nums, int k) {
        // 首先对数组进行排序，以便后续的二分搜索
        Arrays.sort(nums);
        int n = nums.length, left = 0, right = nums[n - 1] - nums[0];
        // 设置二分搜索的范围，left为最小可能距离，right为最大可能距离

        while (left <= right) {
            int mid = (left + right) / 2; // 计算中间距离
            int cnt = 0; // 统计小于等于mid距离的数对数量
            for (int j = 0; j < n; j++) {
                // 对于每个nums[j]，使用二分搜索找到最右边的位置i，使得nums[j] - nums[i] <= mid
                int i = binarySearch(nums, j, nums[j] - mid);
                cnt += j - i; // 累加当前距离内数对的数量
            }
            if (cnt >= k) {
                // 如果小于等于mid距离的数对数量大于等于k，说明第k小的距离对可能更小，缩小搜索范围
                right = mid - 1;
            } else {
                // 如果小于等于mid距离的数对数量小于k，说明第k小的距离对可能更大，扩大搜索范围
                left = mid + 1;
            }
        }
        // 当循环结束时，left指向的就是第k小的距离对
        return left;
    }

    public static int binarySearch(int[] nums, int end, int target) {
        // 这个辅助函数用于找到数组nums中从0到end索引范围内，最右边的位置i，使得nums[i] <= target
        int left = 0, right = end;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                // 如果nums[mid]小于target，说明i可能在mid的右边，移动left指针
                left = mid + 1;
            } else {
                // 如果nums[mid]大于等于target，说明i可能在mid的左边或就是mid，移动right指针
                right = mid;
            }
        }
        // 当循环结束时，left指向的就是最右边的位置i
        return left;
    }

    public int smallestDistancePair2(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, left = 0, right = nums[n - 1] - nums[0];
        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = 0;
            for (int i = 0, j = 0; j < n; j++) {
                while (nums[j] - nums[i] > mid) {
                    i++;
                }
                cnt += j - i;
            }
            if (cnt >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
